#include "../comm.h"
class Solution {
public:
    long long minimumMoves(vector<int>& nums, int k, int maxChanges) {
       vector<int> idx;
       int len = 0;
       // 在这里先寻找是否有连续的1
       for(int i = 0; i < nums.size(); ++i)
        {
            if(nums[i] == 0) continue;
            idx.push_back(i);
            int c = 1;
            if(i > 0 && nums[i - 1] == 1)
            {
                ++c;
                if(i > 1 && nums[i - 2] == 1) 
                    ++c;
            }
            len = max(len, c);
        }
        // 如果连续的数已经够了k个，直接返回
        // cout << len << endl;
        if(len >= k) return k - 1;
        // cout << len << endl;
        // 如果 maxchange >= k - c, 优先使用maxchange
        if(maxChanges >= k - len)
            return max(len - 1, 0) + (k - len) * 2ll;

        // 如果maxchange < k -c, 此时要把maxchange用完，并且找到剩下k - maxchange归一的贪心中位数解
        vector<long long> sum(idx.size() + 1);
        for(int i = 0; i < idx.size(); ++i)
            sum[i + 1] = sum[i] + idx[i];
        long long ans = LLONG_MAX;
        int num = k - maxChanges;
        for(int j = num - 1; j < idx.size(); ++j)
        {
            int i = j - num + 1;
            int mid = (i + j) >> 1;
            int pos = idx[mid];
            long long tmp = 0;
            // cout << mid << ' ' << sum[mid] << endl;
            tmp += (long long)(mid - i) * pos - (sum[mid] - sum[i]);
            // cout << mid * pos - sum[mid] << endl;
            // cout << sum[j + 1] <<  ' ' << sum[mid + 1] << endl;
            tmp += (sum[j + 1] - sum[mid + 1]) - (long long)(j - mid) * pos;
            // cout << sum[j + 1] - sum[mid + 1] - (j - mid) * pos << endl; 
            ans = min(ans, tmp);
        }
        return ans + maxChanges * 2ll;
    }
};